/*
 * huffman.cpp
 */

#include "./huffman.h"

// Estructura del nodo
typedef struct nodo {
		int caracter;
		int frecuencia;
		int numero;
		nodo *padre;
		nodo *izquierdo;
		nodo *derecho;
} tNodo;

tNodo *crear_nodo(struct_Huffman * const huffman, int caracter);
void agregar(struct_Huffman * const huffman, int caracter);
void reordenar(struct_Huffman * const huffman, int caracter);
tNodo *buscar(struct_Huffman * const huffman, tNodo *n);
void intercambiar(struct_Huffman * const huffman, tNodo *n1, tNodo *n2);
void codificar(struct_Huffman * const huffman, FILE *archivoSalidaHandler, tNodo *n);
void emitir(struct_Huffman * const huffman, FILE *archivoSalidaHandler, int caracter);
void vaciar_buffer(struct_Huffman * const huffman, FILE *archivoSalidaHandler);
int decodificar(struct_Huffman * const huffman, FILE *archivoEntradaHandler);
int leer_bit(struct_Huffman * const huffman, FILE *archivoEntradaHandler);
int leer_byte(struct_Huffman * const huffman, FILE *archivoEntradaHandler);
void borrar_arbol(tNodo *n);

// Crear arbol
void huffman_inicializar(struct_Huffman * const huffman) {
	huffman->buffer_huffman = 0;
	huffman->contador_bits = 0;
	huffman->numero = MAXIMO;

	int caracter = 0;

	// crear primer nodo del arbol de Huffman: raiz y escape a la vez
	huffman->escape = crear_nodo(huffman, ESCAPE);
	huffman->raiz = huffman->escape;

	// definir frecuencias iniciales para algunos caracteres
	// (valores obtenidos empiricamente)
	huffman->frecuencias[0] = 2;
	huffman->hojas[0] = 0;
	huffman->frecuencias[1] = 2;
	huffman->hojas[1] = 0;
	for (caracter = 2; caracter < 50; caracter++) {
		huffman->frecuencias[caracter] = 1;
		huffman->hojas[caracter] = 0;
	}
	for (caracter = 50; caracter < RANGO; caracter++) {
		huffman->frecuencias[caracter] = 0;
		huffman->hojas[caracter] = 0;
	}
	for (caracter = 0; caracter < MAXIMO; caracter++) {
		huffman->nodos[caracter] = 0;
	}
	// agregar al arbol los caracteres con frecuencias precargadas
	for (caracter = 0; caracter < RANGO; caracter++) {
		if (huffman->frecuencias[caracter] > 0) {
			agregar(huffman, caracter);
			reordenar(huffman, caracter);
		}
	}
}

// Comprimir usando el algoritmo de Huffman dinamico FGK
void huffman_comprimir(struct_Huffman * const huffman, FILE *archivoSalidaHandler, unsigned char * const bloque, unsigned int longitud) {
	unsigned char caracter = 0;
	unsigned int i = 0;

	// ciclo: codificar, agregar, emitir y reordenar
	for (i = 0; i < longitud; i++) {
		caracter = bloque[i];
		if (huffman->hojas[caracter]) {  // si ya estaba
			codificar(huffman, archivoSalidaHandler, huffman->hojas[caracter]);
		} else {  // si no estaba
			codificar(huffman, archivoSalidaHandler, huffman->escape);
			agregar(huffman, caracter);
			emitir(huffman, archivoSalidaHandler, caracter);
		}
		reordenar(huffman, caracter);
	}
}

void huffman_finalizar(struct_Huffman * const huffman, FILE *archivoSalidaHandler) {
	// se escriben los bits restantes
	vaciar_buffer(huffman, archivoSalidaHandler);
}

// Descomprimir usando el algoritmo de Huffman dinamico FGK
void huffman_descomprimir(struct_Huffman * const huffman, FILE *archivoEntradaHandler, unsigned char * const bloque, unsigned int longitud) {
	int caracter;
	unsigned int i = 0;

	// ciclo: decodificar, agregar, emitir y reordenar
	for (i = 0; i < longitud; i++) {
		caracter = decodificar(huffman, archivoEntradaHandler);

		if (caracter == ESCAPE) {  // si es escape
			caracter = leer_byte(huffman, archivoEntradaHandler);  // leer 8 bits
			agregar(huffman, caracter);
		}
		bloque[i] = caracter;
		reordenar(huffman, caracter);
	}
}

// Borrar el arbol recursivamente
void huffman_destruir(struct_Huffman * const huffman) {
	borrar_arbol(huffman->raiz);
}

// Crear un nodo nuevo
tNodo *crear_nodo(struct_Huffman * const huffman, int caracter) {
	tNodo *n = (tNodo*) ::malloc(sizeof(tNodo));
	n->caracter = caracter;
	n->frecuencia = 0;
	n->numero = huffman->numero--;
	n->padre = NULL;
	n->izquierdo = NULL;
	n->derecho = NULL;
	return n;
}

// Agregar un nuevo caracter en el arbol.
// Crea dos nodos hijos del escape:
// el izquierdo sera el nuevo escape,
// el derecho sera el nuevo caracter.
// Actualiza array hojas y array nodos
void agregar(struct_Huffman * const huffman, int caracter) {
	// dos nodos nuevos
	huffman->escape->izquierdo = crear_nodo(huffman, ESCAPE);
	huffman->escape->derecho = crear_nodo(huffman, caracter);

	// conecta sus punteros al padre
	huffman->escape->izquierdo->padre = huffman->escape;
	huffman->escape->derecho->padre = huffman->escape;

	// agrega el hijo derecho al array hojas
	huffman->hojas[caracter] = huffman->escape->derecho;

	// configura el hijo izquierdo como nuevo escape
	huffman->escape->caracter = INTERNO;
	huffman->escape = huffman->escape->izquierdo;

	// agrega los dos nodos al array nodos
	huffman->nodos[huffman->escape->numero] = huffman->escape;
	huffman->nodos[(huffman->hojas[caracter])->numero] = huffman->hojas[caracter];
}

// Reordenar el arbol despues de agregar un caracter
void reordenar(struct_Huffman * const huffman, int caracter) {
	tNodo *n = huffman->hojas[caracter];
	tNodo *mayor = NULL;

	while (n != huffman->raiz) {
		mayor = buscar(huffman, n);  // busca para intercambiar
		if (mayor) intercambiar(huffman, n, mayor);  // si corresponde intercambia
		n->frecuencia++;  // incrementa la frecuencia
		n = n->padre;  // sigue hacia el padre
	}
}

// Buscar un nodo con la misma frecuencia que el nodo suministrado
// y que tenga el mayor numero dentro del arbol
tNodo *buscar(struct_Huffman * const huffman, tNodo *n) {
	tNodo *mayor = NULL;
	int i;

	if (n->padre == huffman->escape->padre) {  // si es hermano del escape
		for (i = n->numero + 1; i < MAXIMO; i++) {
			if (n->frecuencia == huffman->nodos[i]->frecuencia) {
				if (huffman->nodos[i]->caracter != INTERNO) mayor = huffman->nodos[i];
			} else {
				break;
			}
		}
	} else {  // en los demas casos
		for (i = n->numero + 1; i < MAXIMO; i++) {
			if (n->frecuencia == huffman->nodos[i]->frecuencia) {
				mayor = huffman->nodos[i];
			} else {
				break;
			}
		}
	}
	return mayor;
}

// Intercambiar dos nodos
void intercambiar(struct_Huffman * const huffman, tNodo *n1, tNodo *n2) {
	tNodo *padre_aux = NULL;
	tNodo *nodo_aux = NULL;
	int num_aux = 0;

	// intercambio en el arbol
	if (n1->padre->izquierdo == n1) {
		n1->padre->izquierdo = n2;
	} else {
		n1->padre->derecho = n2;
	}

	if (n2->padre->izquierdo == n2) {
		n2->padre->izquierdo = n1;
	} else {
		n2->padre->derecho = n1;
	}

	padre_aux = n1->padre;
	n1->padre = n2->padre;
	n2->padre = padre_aux;

	// intercambio en el array nodos
	nodo_aux = huffman->nodos[n1->numero];
	huffman->nodos[n1->numero] = huffman->nodos[n2->numero];
	huffman->nodos[n2->numero] = nodo_aux;

	// intercambio de numeros
	num_aux = n1->numero;
	n1->numero = n2->numero;
	n2->numero = num_aux;
}

// Codificar un caracter y poner los bits en el buffer.
// Cuando el buffer se llena, escribe bytes a la salida
void codificar(struct_Huffman * const huffman, FILE *archivoSalidaHandler, tNodo *n) {
	int codigo = 0;
	int pila[RANGO];
	int largo = 0;
	int byte = 0;
	int aux = 0;

	// sube por el arbol obteniendo los bits
	while (n->padre) {
		if (n == n->padre->izquierdo) {
			pila[largo] = 0;
		} else {
			pila[largo] = 1;
		}
		largo++;
		n = n->padre;
	}

	// genera el codigo invirtiendo el orden de los bits
	aux = largo;
	while (aux) {
		if (pila[aux - 1]) {
			codigo = (codigo << 1) | 0x00000001;  // bit 1
		} else {
			codigo = codigo << 1;  // bit 0
		}
		aux--;
	}

	// si no hay lugar en el buffer, escribe a la salida
	while ((huffman->contador_bits + largo) > 32) {
		byte = huffman->buffer_huffman >> (huffman->contador_bits - 8);
		::fputc(byte, archivoSalidaHandler);
		huffman->contador_bits -= 8;
	}

	// guarda el codigo en el buffer, y suma los bits
	huffman->buffer_huffman <<= largo;
	huffman->buffer_huffman |= codigo;
	huffman->contador_bits += largo;
}

// Emitir caracter sin codificar y ponerlo en el buffer
void emitir(struct_Huffman * const huffman, FILE *archivoSalidaHandler, int caracter) {
	int byte = 0;

	// si no hay lugar en el buffer, escribe un byte a la salida
	if ((huffman->contador_bits + 8) > 32) {
		byte = huffman->buffer_huffman >> (huffman->contador_bits - 8);
		::fputc(byte, archivoSalidaHandler);
		huffman->contador_bits -= 8;
	}

	// guarda el caracter en el buffer, y suma 8 bits
	huffman->buffer_huffman <<= 8;
	huffman->buffer_huffman |= caracter;
	huffman->contador_bits += 8;
}

// Escribir a la salida los bits restantes en el buffer
// Si es necesario completa con ceros al final
void vaciar_buffer(struct_Huffman * const huffman, FILE *archivoSalidaHandler) {
	int byte = 0;

	while (huffman->contador_bits > 0) {
		if (huffman->contador_bits >= 8) {
			byte = huffman->buffer_huffman >> (huffman->contador_bits - 8);
		} else {
			byte = huffman->buffer_huffman << (8 - huffman->contador_bits);
		}
		::fputc(byte, archivoSalidaHandler);
		huffman->contador_bits -= 8;
	}
}

// Decodificar un codigo y devolver el caracter que representa
int decodificar(struct_Huffman * const huffman, FILE *archivoEntradaHandler) {
	tNodo *n = huffman->raiz;

	while (n->izquierdo)  // mientras tenga hijos
	{
		if (leer_bit(huffman, archivoEntradaHandler)) {
			n = n->derecho;
		} else {
			n = n->izquierdo;
		}
	}
	return n->caracter;  // llego a una hoja
}

// Leer un bit del buffer_huffman.
// Cada 32 bits leidos se carga el buffer con 4 bytes
int leer_bit(struct_Huffman * const huffman, FILE *archivoEntradaHandler) {
	int byte = 0;
	int bit = 0;
	int i = 0;

	if (huffman->contador_bits == 0) {
		for (i = 0; i < 4; i++) {
			huffman->buffer_huffman <<= 8;
			byte = (unsigned char) ::fgetc(archivoEntradaHandler);
			huffman->buffer_huffman |= byte;
			huffman->contador_bits += 8;
		}
	}

	if (huffman->buffer_huffman & 0x80000000) {
		bit = 1;
	} else {
		bit = 0;
	}
	huffman->buffer_huffman <<= 1;
	huffman->contador_bits--;

	return bit;
}

// Leer 8 bits del buffer_huffman
int leer_byte(struct_Huffman * const huffman, FILE *archivoEntradaHandler) {
	int byte = 0;
	int i = 0;

	for (i = 0; i < 8; i++) {
		byte <<= 1;
		byte |= leer_bit(huffman, archivoEntradaHandler);
	}
	return byte;
}

// Borrar el arbol recursivamente
void borrar_arbol(tNodo *n) {
	if (n->izquierdo) borrar_arbol(n->izquierdo);
	if (n->derecho) borrar_arbol(n->derecho);
	free(n);
}
